package temp.链表.设计链表;

//设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针
///引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
//
// 在链表类中实现这些功能：
//
//
// get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
// addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
// addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
// addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加
//到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
// deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
//
//
//
//
// 示例：
//
//
//MyLinkedList linkedList = new MyLinkedList();
//linkedList.addAtHead(1);
//linkedList.addAtTail(3);
//linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
//linkedList.get(1);            //返回2
//linkedList.deleteAtIndex(1);  //现在链表是1-> 3
//linkedList.get(1);            //返回3
//
//
//
//
// 提示：
//
//
// 0 <= index, val <= 1000
// 请不要使用内置的 LinkedList 库。
// get, addAtHead, addAtTail, addAtIndex 和 deleteAtIndex 的操作次数不超过 2000。
//
//
// Related Topics 设计 链表 👍 764 👎 0

import temp.链表.ListNode;

/**
 * 设计链表
 *
 * @author saint
 */
class P707_设计链表 {
    public static void main(String[] args) {
        MyLinkedList solution = new P707_设计链表().new MyLinkedList();
        solution.head = new ListNode(0);
        solution.head.next =new ListNode(1);
        int i = solution.get(2);
        System.out.println("i = " + i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class MyLinkedList {
    public ListNode head;
    public MyLinkedList() {
        head=new ListNode(0);
    }

    public int get(int index) {
        ListNode res = this.head;
        int num=0;
        while(res!=null){
            if(num == index){
                return res.val;
            }
            res = res.next;
            num++;
        }
        return -1;
    }

    public void addAtHead(int val) {
        ListNode listNode = new ListNode(val);
        listNode.next = this.head;
        this.head = listNode;
    }

    public void addAtTail(int val) {
        ListNode pre = new ListNode();
        pre.next = this.head;
        while(pre.next!=null){
            pre = pre.next;
        }
        pre.next =new ListNode(val);
    }

    public void addAtIndex(int index, int val) {
        ListNode pre = new ListNode();
        pre.next = this.head;
        int num=0;
        while(pre.next!=null){
            if(num==index){
                ListNode now = new ListNode(val);
                now.next = pre.next;
                pre.next =now;
            }
            pre=pre.next;
            num++;
        }
        if(num==index){
            pre.next = new ListNode(val);
        }
    }

    public void deleteAtIndex(int index) {
        ListNode pre = new ListNode();
        pre.next = this.head;
        int num=0;
        while(pre.next!=null){
            if(num == index){
                pre.next = pre.next.next;
                return;
            }
            pre=pre.next;
            num++;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
